\section{Transactions and concurrency}

	\subsection{The ACID Characterization}
		\textit{See slides to have full description}
		\begin{itemize}
			\item Atomicity
			\item Consistency
			\item Isolation
			\item Durability
		\end{itemize}
		
	\subsection{Basic steps and transactions}
	
		\textbf{Basic steps :} A basic step for a transaction T is either a read r(x) or a write w(x) of data object x.\\
		\textbf{Transaction :} A transaction $T\ =\ <t_1,\ t_2,\ ...,\ t_n>$ is a finite sequence of steps with each $t_i$ a basic step for T.\\
		\textbf{Schedule :} a schedule for a set of transactions is a specification of the order in which the basic steps will be executed.\\
		The steps of a schedule : Define $Steps(T) = \cup_{i = 1}^{m} Steps(T_i)$\\
		\textbf{Serial schedule : } A schedule S for the set $T = \{T_1, T_2, ..., T_m\}$ of transactions is serial if there is a total ordering.\\
		
	\subsection{Serializability}
	
		
	\subsection{The problem of deadlock}
	
		Consider the following transactions :
		\begin{equation}
			\begin{split}
			T_1 = r_1(x)r_1(y)w_1(x)\\
			T_2 = r_2(y)r_2(x)w_2(y)
			\end{split}
		\end{equation}
	
		Suppose that scheduling of execution begins as follows :
		$wlk_1(x)r_1(x)wlk_2(y)r_2(y)$
		
		\subsubsection{Detection of deadlock}
		
			Let $T = \{T_1, T_2, ..., T_m\}$ be a set of transactions.\\
			A \textbf{lock set} for $T$ is any subset of $\{wlk_i / 1 \leq i \leq m\ and\ x\ is\ a\ data\ object\}$
		
		\subsubsection{Resolution of deadlock}
		
			\paragraph{Pessimistic resolution\\}
				
			Pessimistic resolution may be guaranteed via conservative 2PL,
in which all locks are acquired before the transaction is allowed to proceed.					
				
			\paragraph{Optimistic resolution\\}
			
				It proceeds by choosing a victim transaction to abort when a deadlock is detected.
		
		\subsubsection{Granularity of locks}
		
			\textbf{Question : What size of objects should be locked ? (lock granularity)\\}
			\begin{itemize}
				\item At first thought, it might seem best to lock the smallest possible objects
				\item Finer granularity have the advantage of allowing
increased parallelism due to lesser contention for data objects
				\item However, finer granularity of locks implies greater overhead from lock management.
			\end{itemize}
			
			\textbf{Observation : Different transactions may require different lock granularities}
			
			\paragraph{Multi-granularity locking\\}
			
				\textit{cf slides}